home *** CD-ROM | disk | FTP | other *** search
/ User's Choice Windows CD / User's Choice Windows CD (CMS Software)(1993).iso / utility1 / gs261src.zip / GXDITHER.C < prev    next >
C/C++ Source or Header  |  1993-05-13  |  11KB  |  332 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* gxdither.c */
  20. #include "gx.h"
  21. #include "gxfixed.h"
  22. #include "gxlum.h"
  23. #include "gxmatrix.h"
  24. #include "gzstate.h"
  25. #include "gzdevice.h"
  26. #include "gzcolor.h"
  27. #include "gzht.h"
  28.  
  29. /* 
  30.  *    Improved dithering for Ghostscript.  The underlying device imaging 
  31.  *    model supports dithering between two colors to generate intermediate
  32.  *    shades.  
  33.  *    
  34.  *    The strategy is to first see if the color is either pure white or
  35.  *    pure black.  In this case the problem is trivial.
  36.  *
  37.  *    Next, if the device has high quality colors (at least 32 values
  38.  *    per axis), we ask it to map the color directly.
  39.  *
  40.  *    Next, if the device is black and white, or the color happens
  41.  *    to be achromatic, we perform simple B/W dithering.
  42.  *    
  43.  *    Otherwise, things are a bit more complicated.  If the device 
  44.  *     supports N shades of each R, G and B independently, there are a total 
  45.  *    of N*N*N colors.  These colors form a 3-D grid in a cubical color 
  46.  *    space.  The following dithering technique works by locating the 
  47.  *    color we want in this 3-D color grid and finding the eight colors 
  48.  *     that surround it.  In the case of dithering into 8 colors with 1 
  49.  *    bit for each red, green and blue, these eight colors will always 
  50.  *    be the same.
  51.  *
  52.  *    Now we consider all possible diagonal paths between the eight colors
  53.  *    and chose the path that runs closest to our desired color in 3-D
  54.  *    color space.  There are 28 such paths.  Then we find the position
  55.  *    on the path that is closest to our color.
  56.  *
  57.  *    The search is made faster by always reflecting our color into
  58.  *    the bottom octant of the cube and comparing it to 7 paths.
  59.  *    After the best path and the best position on that path are found,
  60.  *    the results are reflected back into the original color space.
  61.  *
  62.  *    NOTE: This code has been tested for B/W and Color imaging with
  63.  *    1, 2, 3 and 8 bits per component.
  64.  *
  65.  *    --- original code by Paul Haeberli @ Silicon Graphics - 1990
  66.  *    --- extensively revised by L. Peter Deutsch, Aladdin Enterprises
  67.  */
  68.  
  69. extern void gx_color_load(P2(gx_device_color *, gs_state *));
  70.  
  71. #define    WEIGHT1        (unsigned long)(100)    /* 1.0             */
  72. #define    WEIGHT2        (unsigned long)(71)    /* 1/sqrt(2.0)         */
  73. #define    WEIGHT3        (unsigned long)(62)    /* 1/sqrt(3.0)+tad     */
  74.  
  75. #define    DIAG_R        (0x1)
  76. #define    DIAG_G        (0x2)
  77. #define    DIAG_B        (0x4)
  78. #define    DIAG_RG        (0x3)
  79. #define    DIAG_GB        (0x6)
  80. #define    DIAG_BR        (0x5)
  81. #define    DIAG_RGB    (0x7)
  82.  
  83. private const unsigned short lum_w[8] = {
  84.     (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight),
  85.     (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight),
  86.     (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight),
  87.     (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight),
  88.     (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight),
  89.     (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight),
  90.     (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight),
  91.     (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight),
  92. };
  93.  
  94. /* Compute a fractional color, the correctly rounded quotient of */
  95. /* f * max_gx_color_value / maxv. */
  96. #define _fc(f, maxv)\
  97.   (gx_color_value)(((f) * (0xffffL * 2) + maxv) / (maxv * 2))
  98. /* We have to split up the following because of a bug in the IBM AIX 3.2 */
  99. /* C compiler. */
  100. private const gx_color_value
  101.   q0[] = { 0 };
  102. private const gx_color_value
  103.   q1[] = { 0, _fc(1,1) };
  104. private const gx_color_value
  105.   q2[] = { 0, _fc(1,2), _fc(2,2) };
  106. private const gx_color_value
  107.   q3[] = { 0, _fc(1,3), _fc(2,3), _fc(3,3) };
  108. private const gx_color_value
  109.   q4[] = { 0, _fc(1,4), _fc(2,4), _fc(3,4), _fc(4,4) };
  110. private const gx_color_value
  111.   q5[] = { 0, _fc(1,5), _fc(2,5), _fc(3,5), _fc(4,5), _fc(5,5) };
  112. private const gx_color_value
  113.   q6[] = { 0, _fc(1,6), _fc(2,6), _fc(3,6), _fc(4,6), _fc(5,6), _fc(6,6) };
  114. private const gx_color_value
  115.   q7[] = { 0, _fc(1,7), _fc(2,7), _fc(3,7), _fc(4,7), _fc(5,7), _fc(6,7), _fc(7,7) };
  116. private const gx_color_value _ds *color_quo[8] =
  117.  { q0, q1, q2, q3, q4, q5, q6, q7 };
  118. #define fractional_color(f, maxv)\
  119.   ((maxv) <= 7 ? color_quo[maxv][f] : _fc(f, maxv))
  120.  
  121. /* Render a gray, possibly by halftoning. */
  122. void
  123. gx_render_gray(frac gray, gx_device_color *pdevc, gs_state *pgs)
  124. {    device *pdev = pgs->device;
  125.     gx_device *dev;
  126.     uint max_value;
  127.     unsigned long hsize;
  128.     dev_proc_map_rgb_color((*map_rgb_color));
  129.  
  130. /* Make a special check for black and white. */
  131.     if ( gray == frac_0 )
  132.        {    pdevc->color2 = pdevc->color1 = pdev->black;
  133.         pdevc->halftone_level = 0; /* pure color */
  134.         return;
  135.        }
  136.     else if ( gray == frac_1 )
  137.        {    pdevc->color2 = pdevc->color1 = pdev->white;
  138.         pdevc->halftone_level = 0; /* pure color */
  139.         return;
  140.        }
  141.  
  142. /* get a few handy values */
  143.     dev = pdev->info;
  144.     map_rgb_color = dev->procs->map_rgb_color;
  145.     hsize = (unsigned)pgs->halftone->order_size;
  146.     max_value = dev->color_info.dither_gray - 1;
  147.        {    unsigned long nshades = hsize * max_value + 1;
  148.         unsigned long lx = (nshades * gray) / (frac_1_long + 1);
  149.         uint v = lx / hsize;
  150.         gx_color_value lum = fractional_color(v, max_value);
  151.         pdevc->halftone_level = lx % hsize;
  152.         pdevc->color1 = (*map_rgb_color)(dev, lum, lum, lum);
  153.         if ( pdevc->halftone_level == 0 )
  154.            {    /* Close enough to a pure color, */
  155.             /* no dithering needed. */
  156.             pdevc->color2 = pdevc->color1;
  157.            }
  158.         else
  159.            {    lum = fractional_color(v+1, max_value);
  160.             pdevc->color2 =
  161.                 (*map_rgb_color)(dev, lum, lum, lum);
  162.            }
  163.         gx_color_load(pdevc, pgs);
  164.        }
  165.     return;
  166. }
  167.  
  168. /* Render RGB, possibly by halftoning. */
  169. void
  170. gx_render_rgb(frac red, frac green, frac blue,
  171.   gx_device_color *pdevc, gs_state *pgs)
  172. {    device *pdev = pgs->device;
  173.     gx_device *dev = pdev->info;
  174.     uint max_value = dev->color_info.dither_rgb - 1;
  175.     unsigned long hsize = (unsigned)pgs->halftone->order_size;
  176.     dev_proc_map_rgb_color((*map_rgb_color)) = dev->procs->map_rgb_color;
  177.     frac rem_r = red;
  178.     frac rem_g = green;
  179.     frac rem_b = blue;
  180.     uint r, g, b;
  181.     int adjust_r, adjust_b, adjust_g;
  182.     frac amax;
  183.     unsigned long dmax;
  184.     int axisc, diagc;
  185.     unsigned short lum_invert;
  186.     unsigned long dot1, dot2, dot3;
  187.     int level;
  188.  
  189.     /* Compute the quotient and remainder of each color component */
  190.     /* with the actual number of available colors. */
  191.     switch ( max_value )
  192.        {
  193.     case 1:            /* 8 colors */
  194.         if ( rem_r == frac_1 ) rem_r = 0, r = 1;
  195.         else r = 0;
  196.         if ( rem_g == frac_1 ) rem_g = 0, g = 1;
  197.         else g = 0;
  198.         if ( rem_b == frac_1 ) rem_b = 0, b = 1;
  199.         else b = 0;
  200.         break;
  201.     default:
  202.        {    unsigned long want_r = (ulong)max_value * rem_r;
  203.         unsigned long want_g = (ulong)max_value * rem_g;
  204.         unsigned long want_b = (ulong)max_value * rem_b;
  205.         /* We observe that if M = 2^n-1 and V < M^2, then */
  206.         /*    V / M = (V + (V >> n) + 1) >> n    */
  207.         /*    V % M = (V + (V / M)) & M    */
  208.         r = ((want_r >> frac_bits) + want_r + 1) >> frac_bits;
  209.         g = ((want_g >> frac_bits) + want_g + 1) >> frac_bits;
  210.         b = ((want_b >> frac_bits) + want_b + 1) >> frac_bits;
  211.         rem_r = ((uint)want_r + r) & frac_1;
  212.         rem_g = ((uint)want_g + g) & frac_1;
  213.         rem_b = ((uint)want_b + b) & frac_1;
  214.        }
  215.        }
  216.  
  217.     /* Check for no dithering required */
  218.     if ( !(rem_r | rem_g | rem_b) )
  219.        {    pdevc->color2 = pdevc->color1 =
  220.             (*map_rgb_color)(dev, fractional_color(r, max_value),
  221.                      fractional_color(g, max_value),
  222.                      fractional_color(b, max_value));
  223.         pdevc->halftone_level = 0;
  224.         return;
  225.        }
  226.  
  227.     if_debug9('c', "[c]rgb=%x,%x,%x -->\n   %x+%x,%x+%x,%x+%x -->\n",
  228.           (unsigned)red, (unsigned)green, (unsigned)blue,
  229.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  230.           (unsigned)b, (unsigned)rem_b);
  231.  
  232. /* flip the remainder color into the 0, 0, 0 octant */
  233.     lum_invert = 0;
  234. #define half (frac_1/2)
  235.     if ( rem_r > half )
  236.         rem_r = frac_1 - rem_r,
  237.           adjust_r = -1, r++, lum_invert += lum_red_weight;
  238.     else
  239.         adjust_r = 1;
  240.     if ( rem_g > half )
  241.         rem_g = frac_1 - rem_g,
  242.           adjust_g = -1, g++, lum_invert += lum_green_weight;
  243.     else
  244.         adjust_g = 1;
  245.     if ( rem_b > half )
  246.         rem_b = frac_1 - rem_b,
  247.           adjust_b = -1, b++, lum_invert += lum_blue_weight;
  248.     else
  249.         adjust_b = 1;
  250.     pdevc->color1 = (*map_rgb_color)(dev, fractional_color(r, max_value),
  251.                      fractional_color(g, max_value),
  252.                      fractional_color(b, max_value));
  253. /* 
  254.  * Dot the color with each axis to find the best one of 7;
  255.  * find the color at the end of the axis chosen.
  256.  */
  257.     if ( rem_g > rem_r )
  258.        {    if ( rem_b > rem_g )
  259.             amax = rem_b, axisc = DIAG_B;
  260.         else
  261.             amax = rem_g, axisc = DIAG_G;
  262.         if ( rem_b > rem_r )
  263.             dmax = (unsigned long)rem_g+rem_b, diagc = DIAG_GB;
  264.         else
  265.             dmax = (unsigned long)rem_r+rem_g, diagc = DIAG_RG;
  266.        }
  267.     else
  268.        {    if ( rem_b > rem_r )
  269.             amax = rem_b, axisc = DIAG_B;
  270.         else
  271.             amax = rem_r, axisc = DIAG_R;
  272.         if ( rem_b > rem_g )
  273.             dmax = (unsigned long)rem_b+rem_r, diagc = DIAG_BR;
  274.         else
  275.             dmax = (unsigned long)rem_r+rem_g, diagc = DIAG_RG;
  276.        }
  277.  
  278.     dot1 = amax*WEIGHT1;
  279.     dot2 = dmax*WEIGHT2;
  280.     dot3 = (ulong)rem_r+rem_g+rem_b;    /* rgb axis */
  281.     if ( dot1 > dot2 )
  282.        {    if ( dot3*WEIGHT3 > dot1 )
  283.             diagc = DIAG_RGB,
  284.               level = (hsize * dot3) / (3 * frac_1_long);
  285.         else
  286.             diagc = axisc,
  287.               level = (hsize * amax) / frac_1_long;
  288.        }
  289.     else
  290.        {    if ( dot3*WEIGHT3 > dot2 )
  291.             diagc = DIAG_RGB,
  292.               level = (hsize * dot3) / (3 * frac_1_long);
  293.         else
  294.             level = (hsize * dmax) / (2 * frac_1_long);
  295.        };
  296.  
  297.     if_debug9('c', "   %x+%x,%x+%x,%x+%x; adjust=%d,%d,%d;\n",
  298.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  299.           (unsigned)b, (unsigned)rem_b,
  300.           adjust_r, adjust_g, adjust_b);
  301.  
  302.     if ( (pdevc->halftone_level = level) == 0 )
  303.         pdevc->color2 = pdevc->color1;
  304.     else
  305.        {    gx_color_index color2;
  306. /* construct the second color, inverting back to original space if needed */
  307.         if (diagc & DIAG_R) r += adjust_r;
  308.         if (diagc & DIAG_G) g += adjust_g;
  309.         if (diagc & DIAG_B) b += adjust_b;
  310. /* get the second device color, sorting by luminance */
  311.         color2 = (*map_rgb_color)(dev, fractional_color(r, max_value),
  312.                       fractional_color(g, max_value),
  313.                       fractional_color(b, max_value));
  314. /****** THIS IS A BAD IDEA ******/
  315. #if 0
  316.         if ( lum_w[diagc] < lum_invert )
  317.            {    pdevc->color2 = pdevc->color1;
  318.             pdevc->color1 = color2;
  319.             pdevc->halftone_level = level = hsize - level;
  320.            }
  321.         else
  322. #endif
  323.             pdevc->color2 = color2;
  324.         gx_color_load(pdevc, pgs);
  325.        }
  326.  
  327.     if_debug5('c', "[c]diagc=%d; color1=%lx, color2=%lx, level=%d/%d\n",
  328.           diagc, (ulong)pdevc->color1, (ulong)pdevc->color2,
  329.           level, (unsigned)hsize);
  330.  
  331. }
  332.